package com.hyq.grid.algorithm;

import com.hyq.grid.common.tools;

import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.List;


public class MyAlgo {
    public MyAlgo(List<Map> border, Double distance) {
        this.distance = distance;
        borderOri = border;
        borderPoints = new ArrayList<>();
        for (int i = 0; i < border.size(); i++) {
            borderPoints.add(new Point2D.Double(Double.parseDouble((border.get(i).get("X")).toString()), Double.parseDouble((border.get(i).get("Y")).toString())));
        }
    }


    //    private List<Map<String, Double>> border;
    private List<Point2D.Double> borderPoints;
    private Double distance;
    List<Map> borderOri;

    public Map<String, Object> hexagon() {

//        获取边界矩形范围
        Map boundary = getboundary();

        Double minX = Double.parseDouble(boundary.get("minX").toString());
        Double minY = Double.parseDouble(boundary.get("minY").toString());
        Double maxX = Double.parseDouble(boundary.get("maxX").toString());
        Double maxY = Double.parseDouble(boundary.get("maxY").toString());
        int xSize = (int) Math.ceil((maxX - minX) / (3 * distance));
        int ySIze = (int) Math.ceil((maxY - minY) / (Math.sqrt(3) * distance / 2));

//        箱式索引信息
        Map boxIndex = creatBacGrid(distance);
        List<List> boxes = (List<List>) boxIndex.get("boxes");
        Point.Double startPoint = (Point2D.Double) boxIndex.get("startPoint");
        int boxXSize = (int) boxIndex.get("XLength");
        int boxYSize = (int) boxIndex.get("YLength");
        Double boxPrecision = (Double) boxIndex.get("precision");

        List<Double[]> node = new ArrayList<>(); //节点
        List<Map> element = new ArrayList<>(); //单元
        List<Integer[]> elementIndex = new ArrayList<>(); //索引单元
        List<List> neighbor = new ArrayList<>(); //邻界关系
        int[][] ijToelememnt = new int[ySIze + 1][xSize + 1];
        for (int i = 0; i < ijToelememnt.length; i++) {
            for (int j = 0; j < ijToelememnt[i].length; j++) ijToelememnt[i][j] = -1;
        }
        for (int i = 0; i <= ySIze; i++) {
            for (int j = 0; j <= xSize; j++) {
                Double x = minX + 3 * j * distance;

                if (i % 2 == 0) {
                    x += distance * 3 / 2;
                }

                double y = minY + Math.sqrt(3) * i * distance / 2;

                List<Point2D.Double> currentPoints = new ArrayList<>();
                currentPoints.add(new Point2D.Double(x - distance, y));
                currentPoints.add(new Point2D.Double(x - distance / 2, y + Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x + distance / 2, y + Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x + distance, y));
                currentPoints.add(new Point2D.Double(x + distance / 2, y - Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x - distance / 2, y - Math.sqrt(3) / 2 * distance));

                boolean isIn = false; //判断六边形是否在区域内
                for (Point2D.Double tempPoint : currentPoints) {
                    if (IsPtInPoly(tempPoint, borderPoints)) {

                        node.add(new Double[]{currentPoints.get(0).x, currentPoints.get(0).y});
                        node.add(new Double[]{currentPoints.get(1).x, currentPoints.get(1).y});
                        node.add(new Double[]{currentPoints.get(2).x, currentPoints.get(2).y});
                        node.add(new Double[]{currentPoints.get(3).x, currentPoints.get(3).y});
                        node.add(new Double[]{currentPoints.get(4).x, currentPoints.get(4).y});
                        node.add(new Double[]{currentPoints.get(5).x, currentPoints.get(5).y});

                        Double[] elementX = new Double[6];
                        Double[] elementY = new Double[6];

                        elementX[0] = currentPoints.get(0).x;
                        elementY[0] = currentPoints.get(0).y;

                        elementX[1] = currentPoints.get(1).x;
                        elementY[1] = currentPoints.get(1).y;

                        elementX[2] = currentPoints.get(2).x;
                        elementY[2] = currentPoints.get(2).y;

                        elementX[3] = currentPoints.get(3).x;
                        elementY[3] = currentPoints.get(3).y;

                        elementX[4] = currentPoints.get(4).x;
                        elementY[4] = currentPoints.get(4).y;


                        elementX[5] = currentPoints.get(5).x;
                        elementY[5] = currentPoints.get(5).y;

                        Map<String, Double[]> elementMap = new HashMap<>();
                        elementMap.put("X", elementX);
                        elementMap.put("Y", elementY);

//                        坐标单元
                        element.add(elementMap);

//                        装箱
                        int xCount = (int) Math.floor((x - startPoint.x) / distance);
                        int yCount = (int) Math.floor((y - startPoint.y) / distance);
                        List<Integer> surroundboxes = tools.GetBoxIndex(elementX, elementY, startPoint, boxPrecision, boxXSize, boxYSize, new int[]{xCount, yCount});

                        for (Integer currentboxes : surroundboxes) {
//
                            List<Integer> curcontain = (List<Integer>) boxes.get(currentboxes);
                            curcontain.add(element.size() - 1);
                        }
                        isIn = true;

//                        记录ij对应的单元索引

                        ijToelememnt[i][j] = element.size() - 1;
//                        索引单元
                        int nodesize = node.size();
                        elementIndex.add(new Integer[]{nodesize - 6, nodesize - 5, nodesize - 4, nodesize - 3, nodesize - 2, nodesize - 1});
                        //                        邻接关系
                        Map<String, Object> neighborMap = new HashMap<>();


                        neighborMap.put("elementID", element.size() - 1);
                        List<Integer> neighborIDTemp = new ArrayList<>();
                        //邻接单元索引
                        int[] topNei = new int[3];

                        if (i % 2 == 0) {
                            if ((i - 1) < 0) {
                                topNei[0] = -1;

                            } else {
                                topNei[0] = ijToelememnt[i - 1][j];

                            }

                            if ((j + 1) > xSize || (i - 1) < 0) {
                                topNei[2] = -1;
                            } else {
                                topNei[2] = ijToelememnt[i - 1][j + 1];
                            }

                        } else {

                            if ((i - 1) < 0) {
                                topNei[0] = -1;
                                topNei[2] = -1;
                            } else {
                                topNei[2] = ijToelememnt[i - 1][j];
                                if ((j - 1) < 0) {
                                    topNei[0] = -1;
                                } else {
                                    topNei[0] = ijToelememnt[i - 1][j - 1];
                                }

                            }

                        }

                        if ((i - 2) < 0) {
                            topNei[1] = -1;
                        } else {
                            topNei[1] = ijToelememnt[i - 2][j];
                        }


                        for (int elementint : topNei) {
                            if (elementint != -1) {
                                neighborIDTemp.add(elementint);
                                List<Integer> tempfore = (List<Integer>) neighbor.get(elementint);
                                tempfore.add(element.size() - 1);
                            }
                        }

                        neighborMap.put("neighbor", neighborIDTemp);

                        neighbor.add(neighborIDTemp);
                        break;
                    }
                }

                if (!isIn) {
                    ijToelememnt[i][j] = -1;
                }


            }
        }


        Map<String, Object> returndata = new HashMap<>();
        returndata.put("node", node);
        returndata.put("element", element);
        returndata.put("elementIndex", elementIndex);
        returndata.put("neighbor", neighbor);
        returndata.put("boxIndex", boxIndex);


        return returndata;
    }

    /**
     * @return 返回值带了箱式索引信息的六边形生成算法
     */
    public Map<String, Object> hexagon1() {

//        获取边界矩形范围
        Map boundary = getboundary();

        Double minX = Double.parseDouble(boundary.get("minX").toString());
        Double minY = Double.parseDouble(boundary.get("minY").toString());
        Double maxX = Double.parseDouble(boundary.get("maxX").toString());
        Double maxY = Double.parseDouble(boundary.get("maxY").toString());
        int xSize = (int) Math.ceil((maxX - minX) / (3 * distance));
        int ySIze = (int) Math.ceil((maxY - minY) / (Math.sqrt(3) * distance / 2));

//        箱式索引信息
        Map boxIndex = creatBacGrid(distance);
        List<List> boxes = (List<List>) boxIndex.get("boxes");
        Point.Double startPoint = (Point2D.Double) boxIndex.get("startPoint");
        int boxXSize = (int) boxIndex.get("XLength");
        int boxYSize = (int) boxIndex.get("YLength");
        Double boxPrecision = (Double) boxIndex.get("precision");

        List<Double[]> node = new ArrayList<>(); //节点
        List<Map> element = new ArrayList<>(); //单元
        List<Integer[]> elementIndex = new ArrayList<>(); //索引单元
        List<List> neighbor = new ArrayList<>(); //邻界关系
        int[][] ijToelememnt = new int[ySIze + 1][xSize + 1];
        for (int i = 0; i < ijToelememnt.length; i++) {
            for (int j = 0; j < ijToelememnt[i].length; j++) ijToelememnt[i][j] = -1;
        }
        for (int i = 0; i <= ySIze; i++) {
            for (int j = 0; j <= xSize; j++) {
                Double x = minX + 3 * j * distance;

                if (i % 2 == 0) {
                    x += distance * 3 / 2;
                }

                double y = minY + Math.sqrt(3) * i * distance / 2;

                List<Point2D.Double> currentPoints = new ArrayList<>();
                currentPoints.add(new Point2D.Double(x - distance, y));
                currentPoints.add(new Point2D.Double(x - distance / 2, y + Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x + distance / 2, y + Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x + distance, y));
                currentPoints.add(new Point2D.Double(x + distance / 2, y - Math.sqrt(3) / 2 * distance));
                currentPoints.add(new Point2D.Double(x - distance / 2, y - Math.sqrt(3) / 2 * distance));

                boolean isIn = false; //判断六边形是否在区域内
                for (Point2D.Double tempPoint : currentPoints) {
                    if (IsPtInPoly(tempPoint, borderPoints)) {
                        List<Double[]> hexpoints = new ArrayList<>();
                        for (int k = 0; k < currentPoints.size(); k++) {
                            hexpoints.add(new Double[]{currentPoints.get(k).x, currentPoints.get(k).y});
                        }

                        if (i == 0) {
                            for (int k = 0; k < hexpoints.size(); k++) {
                                node.add(hexpoints.get(k));
                            }
//                            索引单元
                            int nodeSize = node.size();
                            elementIndex.add(new Integer[]{nodeSize - 6, nodeSize - 5, nodeSize - 4, nodeSize - 3, nodeSize - 2, nodeSize - 1});

                        } else {
                            Integer[] hexElementIndex = new Integer[6];
                            for (int k = 0; k < hexpoints.size(); k++) {
                                int nodeIndex = tools.IsArrayIncludes(node, hexpoints.get(k));
                                if (nodeIndex == -1) {
                                    node.add(hexpoints.get(k));
                                    hexElementIndex[k] = node.size() - 1;
                                } else {
                                    hexElementIndex[k] = nodeIndex;
                                }

                            }
                            elementIndex.add(hexElementIndex);
                        }


                        Double[] elementX = new Double[6];
                        Double[] elementY = new Double[6];

                        elementX[0] = currentPoints.get(0).x;
                        elementY[0] = currentPoints.get(0).y;

                        elementX[1] = currentPoints.get(1).x;
                        elementY[1] = currentPoints.get(1).y;

                        elementX[2] = currentPoints.get(2).x;
                        elementY[2] = currentPoints.get(2).y;

                        elementX[3] = currentPoints.get(3).x;
                        elementY[3] = currentPoints.get(3).y;

                        elementX[4] = currentPoints.get(4).x;
                        elementY[4] = currentPoints.get(4).y;


                        elementX[5] = currentPoints.get(5).x;
                        elementY[5] = currentPoints.get(5).y;

                        Map<String, Double[]> elementMap = new HashMap<>();
                        elementMap.put("X", elementX);
                        elementMap.put("Y", elementY);

//                        坐标单元
                        element.add(elementMap);

//                        装箱
                        int xCount = (int) Math.floor((x - startPoint.x) / distance);
                        int yCount = (int) Math.floor((y - startPoint.y) / distance);
                        List<Integer> surroundboxes = tools.GetBoxIndex(elementX, elementY, startPoint, boxPrecision, boxXSize, boxYSize, new int[]{xCount, yCount});

                        for (Integer currentboxes : surroundboxes) {
//
                            List<Integer> curcontain = (List<Integer>) boxes.get(currentboxes);
                            curcontain.add(element.size() - 1);
                        }
                        isIn = true;

//                        记录ij对应的单元索引

                        ijToelememnt[i][j] = element.size() - 1;


                        //                        邻接关系
                        Map<String, Object> neighborMap = new HashMap<>();


                        neighborMap.put("elementID", element.size() - 1);
                        List<Integer> neighborIDTemp = new ArrayList<>();
                        //邻接单元索引
                        int[] topNei = new int[3];

                        if (i % 2 == 0) {
                            if ((i - 1) < 0) {
                                topNei[0] = -1;

                            } else {
                                topNei[0] = ijToelememnt[i - 1][j];

                            }

                            if ((j + 1) > xSize || (i - 1) < 0) {
                                topNei[2] = -1;
                            } else {
                                topNei[2] = ijToelememnt[i - 1][j + 1];
                            }

                        } else {

                            if ((i - 1) < 0) {
                                topNei[0] = -1;
                                topNei[2] = -1;
                            } else {
                                topNei[2] = ijToelememnt[i - 1][j];
                                if ((j - 1) < 0) {
                                    topNei[0] = -1;
                                } else {
                                    topNei[0] = ijToelememnt[i - 1][j - 1];
                                }

                            }

                        }

                        if ((i - 2) < 0) {
                            topNei[1] = -1;
                        } else {
                            topNei[1] = ijToelememnt[i - 2][j];
                        }


                        for (int elementint : topNei) {
                            if (elementint != -1) {
                                neighborIDTemp.add(elementint);
                                List<Integer> tempfore = (List<Integer>) neighbor.get(elementint);
                                tempfore.add(element.size() - 1);
                            }
                        }

                        neighborMap.put("neighbor", neighborIDTemp);

                        neighbor.add(neighborIDTemp);
                        break;
                    }
                }

                if (!isIn) {
                    ijToelememnt[i][j] = -1;
                }


            }
        }


        Map<String, Object> returndata = new HashMap<>();
        returndata.put("node", node);
        returndata.put("element", element);
        returndata.put("elementIndex", elementIndex);
        returndata.put("neighbor", neighbor);
        returndata.put("boxIndex", boxIndex);


        return returndata;
    }


    public Map<String, Object> voronoi() throws Exception {
        int tempinttag = 19;
        //        背景网格信息
        Map boxIndex = creatBacGrid(distance);
        List<List> boxes = (List<List>) boxIndex.get("boxes");
        Point.Double boxStartPoint = (Point2D.Double) boxIndex.get("startPoint");
        int xSize = (int) boxIndex.get("XLength");
        int ySize = (int) boxIndex.get("YLength");
        Double boxPrecision = (Double) boxIndex.get("precision");


        Map<String, Object> outPutData = new HashMap<>();
        gmsh mygmsh = new gmsh(borderOri, distance);
        Map delData = mygmsh.gmshAlgo("del2d");

        List<Double[]> node = (List<Double[]>) delData.get("node");
        List<Integer[]> triangleList = (List<Integer[]>) delData.get("elementIndex");
        List<Map> triNeiList = (List<Map>) delData.get("neighbor");

        List<Double[]> vornode = new ArrayList<>();
        List<Integer[]> voronoiList = new ArrayList<>();
        List<Map> voronoiCoorList = new ArrayList<>();

        List<Integer[]> tempTri = new ArrayList<>();
        List<Integer[]> tempTri2 = new ArrayList<>();
        List<Integer> otherNode = new ArrayList<>();
        for (int i = 0; i < node.size(); i++) {
            for (Integer[] trielement : triangleList) {
                if (tools.MoveToFirst(i, trielement) != null) {
                    tempTri.add(tools.MoveToFirst(i, trielement));
                    otherNode.add(trielement[1]);
                    otherNode.add(trielement[2]);
                }
            }

//            将围绕该点的其他点首尾相连 1.找出起始位置（出现过一次的点，如果是闭环则随便选一个） 2.顺序连接
            Integer[] startInfor = new Integer[]{-1, 1}; //第一个数表示列表中的位置，第二个为数组中的位置

            for (int j = 0; j < tempTri.size(); j++) {
                if (tools.SameCount(tempTri.get(j)[1], otherNode).equals(1)) {
                    startInfor[0] = j;
                    startInfor[1] = 1;
                    break;
                }
                if (tools.SameCount(tempTri.get(j)[2], otherNode).equals(1)) {
                    startInfor[0] = j;
                    startInfor[1] = 2;
                    break;
                }
            }

//            顺序相连
            if (tempTri.size() > 0) {
                Integer[] startPoint;
                if (startInfor[0].equals(-1)) {
                    startPoint = tempTri.get(0);
                } else {
                    startPoint = tempTri.get(startInfor[0]);
                }
                if (startInfor[1].equals(2)) {
                    Integer tempchang = startPoint[1];
                    startPoint[1] = startPoint[2];
                    startPoint[2] = tempchang;
                }
                tempTri2.add(startPoint);
                if (startInfor[0].equals(-1)) {
                    tempTri.remove(0);
                } else {
                    tempTri.remove(startInfor[0].intValue());
                }


                Integer exitTag = 0;
                while (tempTri.size() != 0) {
                    for (int j = 0; j < tempTri.size(); j++) {
                        if (tools.BlIsContain(tempTri2.get(tempTri2.size() - 1)[2], tempTri.get(j))) {
                            Integer[] nextTri = tempTri.get(j);

                            if (nextTri[2].equals(tempTri2.get(tempTri2.size() - 1)[2])) {
                                Integer tempchang = nextTri[1];
                                nextTri[1] = nextTri[2];
                                nextTri[2] = tempchang;
                            }

                            tempTri2.add(nextTri);
                            tempTri.remove(j);

                            break;
                        }
                    }
                    exitTag++;
                    if (exitTag.equals(20)) {
                        System.out.println("陷入了死循环");
                        break;
                    }

                }
            }

            Integer[] vornoiElement ;
            Double[] Xout;
            Double[] Yout;

            if (!startInfor[0].equals(-1)) {
                vornoiElement = new Integer[tempTri2.size() +2];
                Xout = new Double[tempTri2.size() + 2];
                Yout = new Double[tempTri2.size() + 2];

                Xout[0] = (node.get(tempTri2.get(0)[0])[0] + node.get(tempTri2.get(0)[1])[0]) / 2;
                Yout[0] = (node.get(tempTri2.get(0)[0])[1] + node.get(tempTri2.get(0)[1])[1]) / 2;

                Xout[Xout.length - 1] = (node.get(tempTri2.get(tempTri2.size() - 1)[0])[0] + node.get(tempTri2.get(tempTri2.size() - 1)[2])[0]) / 2;
                Yout[Yout.length - 1] = (node.get(tempTri2.get(tempTri2.size() - 1)[0])[1] + node.get(tempTri2.get(tempTri2.size() - 1)[2])[1]) / 2;

                Double[] tempCenter1 = new Double[]{Xout[0], Yout[0]};


                int nodeIndex1 = tools.IsArrayIncludes(vornode, tempCenter1);
                if (nodeIndex1 == -1) {
                    vornode.add(tempCenter1);
                    vornoiElement[0] = vornode.size() - 1;
                } else {
                    vornoiElement[0] = nodeIndex1;
                }

                Double[] tempCenter2 = new Double[]{ Xout[Xout.length - 1], Yout[Yout.length - 1]};
                int nodeIndex2 = tools.IsArrayIncludes(vornode, tempCenter2);
                if (nodeIndex2 == -1) {
                    vornode.add(tempCenter2);
                    vornoiElement[vornoiElement.length - 1] = vornode.size() - 1;
                } else {
                    vornoiElement[vornoiElement.length - 1] = nodeIndex2;
                }

            } else {
                vornoiElement = new Integer[tempTri2.size()];
                Xout = new Double[tempTri2.size()];
                Yout = new Double[tempTri2.size()];
            }


            for (int j = 0; j < tempTri2.size(); j++) {
                List<Double[]> points = new ArrayList<>();
                points.add(new Double[]{node.get(tempTri2.get(j)[0])[0], node.get(tempTri2.get(j)[0])[1]});
                points.add(new Double[]{node.get(tempTri2.get(j)[1])[0], node.get(tempTri2.get(j)[1])[1]});
                points.add(new Double[]{node.get(tempTri2.get(j)[2])[0], node.get(tempTri2.get(j)[2])[1]});
                Double[] tempCenter = tools.OutCenterTriangle(points);

//                存储网格单元点信息
                int nodeIndex = tools.IsArrayIncludes(vornode, tempCenter);


                if (!startInfor[0].equals(-1)) {


                    Xout[j + 1] = tempCenter[0];
                    Yout[j + 1] = tempCenter[1];


                    if (nodeIndex == -1) {
                        vornode.add(tempCenter);
                        vornoiElement[j + 1] = vornode.size() - 1;
                    } else {
                        vornoiElement[j + 1] = nodeIndex;
                    }
                } else {
                    Xout[j] = tempCenter[0];
                    Yout[j] = tempCenter[1];

                    if (nodeIndex == -1) {
                        vornode.add(tempCenter);
                        vornoiElement[j] = vornode.size() - 1;
                    } else {
                        vornoiElement[j] = nodeIndex;
                    }
                }

            }

            Map<String, Double[]> voronoiElementMap = new HashMap<>();
            voronoiElementMap.put("X", Xout);
            voronoiElementMap.put("Y", Yout);
            for (int j = 0; j < Xout.length; j++) {
                System.out.println("Pouint(" +tempinttag + ") = {" + Xout[j] + "," + Yout[j] + ",0,lc};");
                tempinttag ++;
            }

            voronoiCoorList.add(voronoiElementMap);

            voronoiList.add(vornoiElement);

//            装箱

            int xCount = (int) Math.floor((node.get(i)[0] - boxStartPoint.x) / distance);
            int yCount = (int) Math.floor((node.get(i)[1] - boxStartPoint.y) / distance);
            List<Integer> surroundboxes = tools.GetBoxIndex(Xout, Yout, boxStartPoint, boxPrecision, xSize, ySize, new int[]{xCount, yCount});

            for (Integer currentboxes : surroundboxes) {
                List<Integer> curcontain = (List<Integer>) boxes.get(currentboxes);
                curcontain.add(i);
            }


            tempTri.clear();
            tempTri2.clear();
            otherNode.clear();

        }

        List<List> neighborList = tools.CreatNeighborList(vornode, voronoiList, boxIndex);


        outPutData.put("node", vornode);
        outPutData.put("element", voronoiCoorList);
        outPutData.put("elementIndex", voronoiList);
        outPutData.put("neighbor", neighborList);
        outPutData.put("boxIndex", boxIndex);

        return outPutData;
    }

    public Map<String, Double> getboundary() {
        Map<String, Double> bound = new HashMap<>();
        Double minX, maxX, minY, maxY;
        minX = borderPoints.get(0).x;
        maxX = borderPoints.get(0).x;
        minY = borderPoints.get(0).y;
        maxY = borderPoints.get(0).y;

        for (int i = 1; i < borderPoints.size(); i++) {
            if (borderPoints.get(i).x < minX) minX = borderPoints.get(i).x;
            if (borderPoints.get(i).x > maxX) maxX = borderPoints.get(i).x;
            if (borderPoints.get(i).y < minY) minY = borderPoints.get(i).y;
            if (borderPoints.get(i).y > maxY) maxY = borderPoints.get(i).y;
        }
        bound.put("minX", minX);
        bound.put("maxX", maxX);
        bound.put("minY", minY);
        bound.put("maxY", maxY);
        return bound;
    }

    public Map<String, Object> square() {
//        获取边界矩形范围
        Map boundary = getboundary();

        Double minX = Double.parseDouble(boundary.get("minX").toString());
        Double minY = Double.parseDouble(boundary.get("minY").toString());
        Double maxX = Double.parseDouble(boundary.get("maxX").toString());
        Double maxY = Double.parseDouble(boundary.get("maxY").toString());
        int xSize = (int) Math.ceil((maxX - minX) / distance);
        int ySIze = (int) Math.ceil((maxY - minY) / distance);

//        输出信息
        List<Double[]> node = new ArrayList<>(); //节点
        List<Map> element = new ArrayList<>(); //单元
        List<Integer[]> elementIndex = new ArrayList<>(); //索引单元
        List<Map> neighbor = new ArrayList<>(); //邻界关系

        List<Point2D.Double> currentSquar = new ArrayList<>();
        for (int i = 0; i < ySIze; i++) {
            for (int j = 0; j < xSize; j++) {
//                获取正方形单元四个点的坐标
                currentSquar.add(new Point2D.Double(minX + j * distance, minY + i * distance));
                currentSquar.add(new Point2D.Double(minX + (j + 1) * distance, minY + i * distance));
                currentSquar.add(new Point2D.Double(minX + (j + 1) * distance, minY + (i + 1) * distance));
                currentSquar.add(new Point2D.Double(minX + j * distance, minY + (i + 1) * distance));


                for (Point2D.Double currentPoint : currentSquar) {
                    if (IsPtInPoly(currentPoint, borderPoints)) {
                        node.add(new Double[]{minX + j * distance, minY + i * distance});
                        node.add(new Double[]{minX + (j + 1) * distance, minY + i * distance});
                        node.add(new Double[]{minX + (j + 1) * distance, minY + (i + 1) * distance});
                        node.add(new Double[]{minX + j * distance, minY + (i + 1) * distance});

//                        存储四边形坐标
                        Double[] elementX = new Double[4];
                        Double[] elementY = new Double[4];

                        elementX[0] = currentSquar.get(0).x;
                        elementY[0] = currentSquar.get(0).y;

                        elementX[1] = currentSquar.get(1).x;
                        elementY[1] = currentSquar.get(1).y;

                        elementX[2] = currentSquar.get(2).x;
                        elementY[2] = currentSquar.get(2).y;

                        elementX[3] = currentSquar.get(3).x;
                        elementY[3] = currentSquar.get(3).y;

                        Map<String, Double[]> elementMap = new HashMap<>();
                        elementMap.put("X", elementX);
                        elementMap.put("Y", elementY);

//                        坐标单元
                        element.add(elementMap);
                        elementIndex.add(new Integer[]{node.size() - 4, node.size() - 3, node.size() - 2, node.size() - 1});

                        break;
                    }
                }
                currentSquar.clear();
            }
        }


        Map<String, Object> returndata = new HashMap<>();
        returndata.put("node", node);
        returndata.put("element", element);
        returndata.put("elementIndex", elementIndex);
        returndata.put("neighbor", neighbor);
        return returndata;
    }

    /**
     * @param point 点
     * @param pts   多边形点列表
     * @return 点在多边形上或在多边形内部返回 true 否则返回false
     */
    public boolean IsPtInPoly(Point2D.Double point, List<Point2D.Double> pts) {

        int N = pts.size();
        boolean boundOrVertex = true; //如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
        int intersectCount = 0;//cross points count of x
        double precision = 2e-10; //浮点类型计算时候与0比较时候的容差
        Point2D.Double p1, p2;//neighbour bound vertices
        Point2D.Double p = point; //当前点

        p1 = pts.get(0);//left vertex
        for (int i = 1; i <= N; ++i) {//check all rays
            if (p.equals(p1)) {
                return boundOrVertex;//p is an vertex
            }

            p2 = pts.get(i % N);//right vertex
            if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {//ray is outside of our interests
                p1 = p2;
                continue;//next ray left point
            }

            if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {//横坐标 内  ray is crossing over by the algorithm (common part of)
                if (p.y <= Math.max(p1.y, p2.y)) {//y下  x is before of ray
                    if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {//overlies on a horizontal ray  垂线
                        return boundOrVertex;
                    }

                    if (p1.y == p2.y) {//水平线 ray is vertical
                        if (p1.y == p.y) {//水平线内 overlies on a vertical ray
                            return boundOrVertex;
                        } else {//before ray
                            ++intersectCount;  //交点在上方
                        }
                    } else {//cross point on the left side
                        double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;//两点式化简，交点y坐标 cross point of y
                        if (Math.abs(p.y - xinters) < precision) {//== 0  在线上  overlies on a ray
                            return boundOrVertex;
                        }

                        if (p.y < xinters) {//before ray
                            ++intersectCount;  //交点在上方
                        }
                    }
                }
            } else {//special case when ray is crossing through the vertex
                if (p.x == p2.x && p.y <= p2.y) {//p crossing over p2
                    Point2D.Double p3 = pts.get((i + 1) % N); //next vertex
                    if (p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)) {//p.x lies between p1.x & p3.x
                        ++intersectCount;
                    } else {
                        intersectCount += 2;
                    }
                }
            }
            p1 = p2;//next ray left point
        }

        if (intersectCount % 2 == 0) {//偶数在多边形外
            return false;
        } else { //奇数在多边形内
            return true;
        }

    }

    public Map creatBacGrid(Double cellLength) {
        Double XMin, YMin, XMax, YMax;
        Double cellsize = cellLength;
        XMin = borderPoints.get(0).x;
        XMax = borderPoints.get(0).x;
        YMin = borderPoints.get(0).y;
        YMax = borderPoints.get(0).y;
        for (Point2D.Double Point : borderPoints) {
            if (Point.x < XMin) XMin = Point.x;
            if (Point.x > XMax) XMax = Point.x;
            if (Point.y < YMin) YMin = Point.y;
            if (Point.y > YMax) YMax = Point.y;
        }


        int xLength = (int) Math.ceil((XMax - XMin) / cellsize);
        int yLength = (int) Math.ceil((YMax - YMin) / cellsize);

        xLength++;
        yLength++;
//        List<Map> bacGrid = new ArrayList<>(xLength * yLength);
        List<List> boxes = new ArrayList<>();
        for (int i = 0; i < yLength; i++) {
            for (int j = 0; j < xLength; j++) {
//                List<Point2D.Double> coordinates = new ArrayList<>();
//                coordinates.add(new Point2D.Double(XMin + j * cellsize, YMin + i * cellsize));
//                coordinates.add(new Point2D.Double(XMin + (j + 1) * cellsize, YMin + i * cellsize));
//                coordinates.add(new Point2D.Double(XMin + (j + 1) * cellsize, YMin + (i + 1) * cellsize));
//                coordinates.add(new Point2D.Double(XMin + j * cellsize, YMin + (i + 1) * cellsize));
//                Map tempE = new HashMap();
                List<Integer> contain = new ArrayList<>();
//                tempE.put("coordinates", coordinates);
//                tempE.put("contain", contain);
//                bacGrid.add(tempE);
                boxes.add(contain);
            }
        }


        Map returnData = new HashMap();
        returnData.put("boxes", boxes);
        returnData.put("XLength", xLength);
        returnData.put("YLength", yLength);
        returnData.put("precision", cellLength);
        returnData.put("startPoint", new Point2D.Double(XMin, YMin));
        return returnData;

    }

}
